home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / asmutil / asm_n_z.zip / SIEVE386.ASM < prev    next >
Assembly Source File  |  1987-04-03  |  7KB  |  261 lines
  1.     title    'Eratosthenes Sieve for 80386'
  2.     name    sieve
  3.     page    50,132
  4.  
  5. ;
  6. ; Eratosthenes Sieve for 80386 32-bit protected mode
  7. ; Implemented by Ray Duncan, April 1987
  8. ; After Gilbreath, Byte September 1981, and January 1983
  9. ;
  10. ; Here is the MAKE file for this program:
  11. ;
  12. ; sieve386.obj : sieve386.asm
  13. ;   386asm sieve386
  14. ; 
  15. ; sieve386.exe : sieve386.obj
  16. ;   386link sieve386 start386 -exe sieve386 -map sieve386
  17. ;
  18. ; To run the program with PharLap DOS|EXTENDER:
  19. ;   C>RUN386 SIEVE386
  20. ;
  21.  
  22. niter    equ     100              ; number of iterations
  23. asize   equ     8190            ; size of array "flags"
  24.  
  25. cr    equ    0dh            ; ASCII carriage return
  26. lf    equ    0ah            ; ASCII line feed
  27.  
  28. stdin    equ     0            ; handle for standard input
  29. stdout    equ    1            ; handle for standard output
  30.  
  31.  
  32. _TEXT    segment para public use32 'CODE'
  33.  
  34.     assume cs:_TEXT,ds:_DATA,es:_DATA
  35.  
  36.     public _start_            ; magic name for RUN386 entry
  37.  
  38. _start_    proc    near
  39.  
  40.     xor    edx,edx            ; convert number of iterations
  41.     mov    eax,niter        ; for output
  42.     mov    ecx,10
  43.     mov    esi,offset msg1a+3
  44.     call    binasc
  45.  
  46.     mov    edx,offset msg1        ; display message
  47.     mov    ecx,msg1_len        ; "Starting N iterations of sieve"
  48.     call    pmsg
  49.  
  50.     call    getmsec            ; get current time in msec
  51.     push    eax            ; and save it...
  52.  
  53.         mov     counter,niter        ; initialize iterations counter
  54.  
  55. sieve1:                    ; a sieve iteration starts here...
  56.     mov    edi,offset flags    ; initialize flags array
  57.     mov    ecx,asize        ; to all bytes = TRUE
  58.     mov    al,1
  59.     cld
  60.     rep stosb
  61.  
  62.      xor    esi,esi            ; ESI = index to flags array
  63.     xor    edi,edi            ; EDI = primes counter
  64.  
  65. sieve2:                     ; main loop of sieve
  66.         test    byte ptr flags[esi],1    ; is this a prime?
  67.     jnz    short sieve4        ; jump if prime
  68.  
  69. sieve3:    inc     esi            ; bump to next slot in "flags"
  70.     cmp    esi,asize
  71.     jle    sieve2            ; loop until array exhausted
  72.  
  73.     dec    counter            ; count off sieve iterations
  74.     jnz    sieve1            ; jump, another iteration needed.
  75.     jmp    sieve7            ; jump, all iterations finished.
  76.  
  77. sieve4:                    ; prime found, zap its multiples
  78.     mov    ebx,esi            ; copy i
  79.      mov     edx,ebx         ; EDX = prime = i + i + 3
  80.         add    edx,edx
  81.         add     edx,3
  82.     xor    al,al
  83.     jmp    short sieve6
  84.  
  85. sieve5:    mov    byte ptr flags[ebx],al    ; zero this multiple
  86.  
  87. sieve6:    add     ebx,edx            ; find next multiple of prime
  88.         cmp     ebx,asize        ; have we exhausted the array?
  89.         jle    sieve5            ; not yet, zap it
  90.     inc     edi            ; count primes and try next
  91.     jmp    sieve3
  92.  
  93. sieve7:    call    getmsec            ; all done, get current time
  94.     push    eax
  95.  
  96.     mov    eax,edi            ; convert number of primes 
  97.     mov    edx,0            ; found on last iteration
  98.     mov    ecx,10
  99.     mov    esi,offset msg2a+4
  100.     call    binasc
  101.  
  102.     mov    edx,offset msg2        ; display "Number of primes: "
  103.     mov    ecx,msg2_len
  104.     call    pmsg
  105.  
  106.     pop    eax            ; calculate total elapsed msec.
  107.     pop    ebx
  108.     sub    eax,ebx
  109.  
  110.     mov    edx,0            ; divide by number of iterations
  111.     mov    ecx,niter        ; to get msec per iteration
  112.     idiv    ecx
  113.  
  114.     mov    edx,0            ; convert msec to ASCII
  115.     mov    ecx,10
  116.     mov    esi,offset msg3a+4
  117.     call    binasc
  118.  
  119.     mov    edx,offset msg3        ; display "Elapsed time:"
  120.     mov    ecx,msg3_len
  121.     call    pmsg
  122.  
  123.      mov     ax,04C00h        ; final exit, return code = 0 
  124.         int     21H
  125.  
  126. _start_    endp
  127.  
  128.  
  129. getmsec    proc    near            ; Return EAX = current time in msec.
  130.  
  131.     mov    ah,2ch            ; read time    
  132.     int    21h
  133.     movzx    eax,ch            ; EAX := hours
  134.     imul    eax,60            ; hours -> minutes
  135.     and    ecx,0ffh        ; isolate system minutes
  136.     add    eax,ecx            ; and find total minutes
  137.     imul    eax,60            ; minutes -> seconds
  138.     movzx    ecx,dh            ; isolate system seconds
  139.     add    eax,ecx            ; and find total seconds
  140.     and    edx,0ffh        ; isolate hundredths
  141.     imul    eax,100            ; seconds -> hundredths
  142.     add    eax,edx            ; find total hundredths
  143.     imul    eax,10            ; hundredths -> msec
  144.     ret
  145.  
  146. getmsec    endp
  147.  
  148. ;
  149. ; BINASC: Convert 64 bit binary value to ASCII string.
  150. ;
  151. ; Call with  EDX:EAX  = signed 64 bit value
  152. ;         ECX      = radix
  153. ;            DS:ESI   = last byte of area to store resulting string
  154. ;                    (make sure enough room is available to store
  155. ;                the string in the radix you have selected.)
  156. ;
  157. ; Destroys EAX, EBX, ECX, EDX, and ESI.
  158. ;
  159. binasc     proc    near            ; convert EDX:EAX to ASCII.
  160.  
  161.     mov    byte ptr [esi],'0'     ; force storage of at least 1 digit.
  162.     or    edx,edx            ; test sign of 64 bit value,
  163.     pushf                ; and save sign on stack.
  164.     jns    bin1            ; jump if it was positive.
  165.     not    edx            ; negative, take 2's complement
  166.     not    eax            ; of the value. 
  167.     add    eax,1
  168.     adc    edx,0
  169. bin1:                    ; divide 64 bit value by the radix 
  170.                     ; to extract next digit for the
  171.                     ; forming string.
  172.     mov    ebx,eax            ; is the value zero yet?
  173.     or    ebx,edx
  174.     jz    bin3            ; yes, we are done converting.
  175.     call    divide            ; no, divide by radix.
  176.     add    bl,'0'            ; convert remainder to ASCII digit.
  177.     cmp    bl,'9'            ; might be converting hex ASCII,
  178.     jle    bin2            ; jump if in range 0-9,
  179.     add    bl,'A'-'9'-1        ; correct it if in range A-F.
  180. bin2:    mov    [esi],bl        ; store this character into string.
  181.     dec    esi            ; back up through string,
  182.     jmp    bin1            ; and do it again.
  183. bin3:                    ; restore sign flag,
  184.     popf                ; was original value negative?
  185.     jns    bin4            ; no, jump
  186.     mov    byte ptr [esi],'-'    ; yes,store sign into output string.
  187. bin4:    ret                ; back to caller.
  188.  
  189. binasc    endp
  190.  
  191. ;
  192. ; General purpose 64 bit by 32 bit unsigned divide.
  193. ; This must be used instead of the plain machine unsigned divide
  194. ; for cases where the quotient may overflow 32 bits.  If called with
  195. ; zero divisor, this routine returns the dividend unchanged and gives 
  196. ; no warning.
  197. ;
  198. ; Call with EDX:EAX = 64 bit dividend
  199. ;           ECX     = divisor
  200. ;
  201. ; Returns   EDX:EAX = quotient
  202. ;           EBX     = remainder
  203. ;        ECX     = divisor (unchanged)
  204. ;
  205. divide    proc    near            ; Divide EDX:EAX by ECX
  206.  
  207.     jecxz    div1            ; exit if divide by zero
  208.     push    eax            ; 0:dividend_upper/divisor
  209.     mov    eax,edx
  210.     xor    edx,edx
  211.     div    ecx
  212.     mov    ebx,eax            ; EBX = quotient1
  213.     pop    eax            ; remainder1:dividend_lower/divisor
  214.     div    ecx
  215.     xchg    ebx,edx            ; EDX:EAX = quotient1:quotient2
  216.  
  217. div1:    ret                ; EBX = remainder2
  218.  
  219. divide    endp
  220.  
  221.  
  222. pmsg    proc    near            ; print a message on std output
  223.                     ; call with DS:EDX = address 
  224.                     ;           ECX    = length 
  225.     mov    ah,40h
  226.     mov    bx,stdout
  227.     int    21h
  228.     ret
  229. pmsg    endp
  230.  
  231. _TEXT    ends
  232.  
  233.  
  234. _DATA    segment para public use32 'DATA'
  235.  
  236.  
  237. flags    db      asize+1 dup (?)
  238. counter    dd      ?            ; sieve iteration counter
  239.  
  240. msg1    db    cr,lf,'Starting '
  241. msg1a    db    '     iterations of Sieve...',cr,lf
  242. msg1_len equ $-msg1
  243.  
  244. msg2    db    cr,lf,'Primes found:  '
  245. msg2a    db    '     ',cr,lf
  246. msg2_len equ $-msg2
  247.  
  248. msg3    db    cr,lf,'Elapsed time:  '
  249. msg3a    db    '       msec. per iteration',cr,lf
  250. msg3_len equ $-msg3
  251.     
  252.  
  253. _DATA    ends
  254.  
  255.  
  256. _STACK    segment byte stack use32 'stack'
  257.           db      4096 dup (?)
  258. _STACK    ends
  259.  
  260.     end
  261.